package hot100;

import DTO.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class pathSum2 {
    public int pathSum1(TreeNode root, int targetSum) {
        Map<Long,Integer> prefix = new HashMap<>();
        prefix.put(0L,1);//放置和为0路径为1条
        return dfs1(root,prefix,0,targetSum);
    }
    public int dfs1(TreeNode root,Map<Long,Integer> prefix,long curr,int targetSum) {
        if(root == null) {
            return 0;
        }
        int ret = 0;
        curr += root.val;//更新和

        ret = prefix.getOrDefault(curr-targetSum,0);//满足 targetSum 的路径数添加到ret中
        prefix.put(curr,prefix.getOrDefault(curr,0)+1);//更新路径数
        ret += dfs1(root.left,prefix,curr,targetSum);
        ret += dfs1(root.right,prefix,curr,targetSum);
        prefix.put(curr,prefix.getOrDefault(curr,0)-1);//剔除重复的影响
        return ret;
    }

    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<>();
        prefix.put(0L, 1); // 初始化：前缀和为0的路径有1条（空路径）
        return dfs(root, prefix, 0, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;
        curr += root.val; // 更新当前路径和

        // 检查是否存在满足条件的前缀和
        ret = prefix.getOrDefault(curr - targetSum, 0);

        // 将当前路径和存入哈希表
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);

        // 递归处理左右子树
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);

        // 回溯：移除当前路径和（避免影响其他分支的统计）
        prefix.put(curr, prefix.get(curr) - 1);

        return ret;
    }
}
